package NO1_Array;

/**
 * 2025-09-15
 * 力扣 - 45. 跳跃游戏 II
 * <p>
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。
 * 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
 * 0 <= j <= nums[i] 且
 * i + j < n
 * 返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。
 */
public class Jump2Main {
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println(jump(nums));
    }

    /**
     * 不会
     */
    public static int jump(int[] nums) {
        int n = nums.length;
        // 特殊情况：数组长度<=1，不需要跳跃
        if (n <= 1) return 0;

        int jumps = 0;          // 记录跳跃次数
        int currentEnd = 0;     // 当前跳跃能到达的最远位置（当前层边界）
        int farthest = 0;       // 下一次跳跃能到达的最远位置（下一层边界）

        // 遍历数组，注意：只需要遍历到 n-2，因为最后一个位置不需要跳跃
        for (int i = 0; i < n - 1; i++) {
            // 更新从当前位置能跳到的最远位置
            farthest = Math.max(farthest, i + nums[i]);

            // 如果已经能跳到终点，提前返回（节省时间）
            if (farthest >= n - 1) {
                return jumps + 1; // 还需要跳最后一次
            }

            // 关键：当遍历到当前层的边界时，说明需要进入下一层
            if (i == currentEnd) {
                jumps++;        // 增加跳跃次数
                currentEnd = farthest; // 更新下一层的边界
            }
        }

        return jumps;
    }
}
